// step 1# 计算数组所有元素的总和
int getSum(int *nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return sum;
}

int findTargetSumWays(int* nums, int numsSize, int target) {
    // step 2# 计算 sum 和 bagSize
    int sum = getSum(nums, numsSize);

    // step 3# 特判：如果 target 的绝对值大于 sum，肯定无解
    if (abs(target) > sum) {
        return 0;
    }

    // step 4# 特判：如果 (sum + target) 是奇数，无解
    if ((sum + target) % 2 != 0) {
        return 0;
    }

    // step 5# 计算背包容量
    int bagSize = (sum + target) / 2;

    // step 6# 定义 dp[i][j]：用前0~i的数，凑出j的方法数
    int dp[numsSize][bagSize + 1];

    // step 7# 初始化
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j <= bagSize; j++) {
            dp[i][j] = 0;
        }
    }
    // step 7.1# 特别初始化：第一个元素
    dp[0][0] = 1; // 什么都不选，和为0，有1种方法
    if (nums[0] <= bagSize) {
        dp[0][nums[0]] += 1; // 如果第一个数本身不超容量，可以作为一种方案
    }

    // step 8# 遍历物品（从第1个开始，即物品编号1）
    for (int i = 1; i < numsSize; i++) {
        int num = nums[i]; // 当前物品的数值

        // step 8.1# 遍历背包容量
        for (int j = 0; j <= bagSize; j++) {

            // step 8.2# 先继承：不选当前物品
            dp[i][j] = dp[i - 1][j];

            // step 8.3# 如果容量够，可以选择放入当前物品
            if (j >= num) {
                dp[i][j] += dp[i - 1][j - num];
            }
        }
    }

    // step 9# 返回使用全部数，凑成 bagSize 的方法总数
    return dp[numsSize - 1][bagSize];
}
